/**
 * 
 */
package leetCode;

import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedList;
import java.util.Map;

/**
 * @author zhongfang
 *
 */
public class SymmetricTree {
	  public class TreeNode {
		      int val;
		      TreeNode left;
		      TreeNode right;
		      TreeNode(int x) { val = x; }
		  }
    public boolean isSymmetric(TreeNode root) {
    	if(root==null){
    		return true;
    	}
    	Deque<TreeNode> queue1=new LinkedList<>();
        Deque<TreeNode> queue2=new LinkedList<>();
        queue1.add(root.left);
        queue1.add(root.right);
        boolean takenFrom1=true;
        while (!queue1.isEmpty()||!queue2.isEmpty()) {
        	Deque<TreeNode> takenQueue=takenFrom1?queue1:queue2;
        	Deque<TreeNode> addQueue=takenFrom1?queue2:queue1;
        	takenFrom1=!takenFrom1;
        	while (!takenQueue.isEmpty()) {
    			TreeNode leftNode=takenQueue.pollFirst();
    			TreeNode rightNode=takenQueue.pollLast();
    			if(leftNode==null&&rightNode==null){
    				continue;
    			}else if (leftNode==null||rightNode==null) {
    				return false;
    			}else {
    				if(leftNode.val!=rightNode.val){
    					return false;
    				}
    				addQueue.addFirst(leftNode.right);
    				addQueue.addFirst(leftNode.left);
    				addQueue.addLast(rightNode.left);
    				addQueue.addLast(rightNode.right);
    			}
    		}
		}
    	return true;
    }
	/**
	 * @param args
	 */
	public static void main(String[] args) {
		SymmetricTree symmetricTree=new SymmetricTree();
		int[] nums={1,2,2,3,4,4,3};
		ArrayList<TreeNode> nodes=new ArrayList<>();
		for (int i : nums) {
			TreeNode node=symmetricTree.new TreeNode(i);
			nodes.add(node);
		}
		for (int i = 0; i < nums.length/2; i++) {
			nodes.get(i).left=nodes.get(2*i+1);
			nodes.get(i).right=nodes.get(2*i+2);
		}
		
		System.out.println(symmetricTree.isSymmetric(nodes.get(0)));
	}

}
